﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Server.Struct
{
    class RootHeap<T>
    {
        readonly static int DEFAULT_CAPCITY = 4;

        List<T> _heap = new List<T>();

        Func<T, T, bool> _compare;

        public bool IsEmpty => _heap.Count < 2;

        public RootHeap()
        {
            _heap = new List<T>(DEFAULT_CAPCITY);
            _heap.Add(default(T));
        }

        public RootHeap(Func<T, T, bool> compare)
        {
            _compare = compare;
            _heap = new List<T>(DEFAULT_CAPCITY);
            _heap.Add(default(T));
        }

        public RootHeap(Func<T, T, bool> compare, Action<T> whenSort)
        {
            _compare = compare;
            _heap = new List<T>(DEFAULT_CAPCITY);
            _heap.Add(default(T));
        }

        public void SetCompare(Func<T, T, bool> compare)
        {
            _compare = compare;
        }

        public virtual T Peek()
        {
            return _heap[1];
        }

        public virtual T Pop()
        {
            if (IsEmpty)
                throw new ArgumentException("RootHeap Is Empty");

            //交换第一个和最后一个
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[1];
            _heap[1] = _heap[lastIndex];
            T ret = _heap[0];
            _heap.RemoveAt(lastIndex);

            lastIndex--;
            //Sort Down
            int index = 1, lindex = index * 2, rindex = lindex + 1;
            int nextIndex = 0;
            while (lindex <= lastIndex)
            {
                if (rindex <= lastIndex && !_compare(_heap[lindex], _heap[rindex]))
                {
                    nextIndex = rindex;
                }
                else
                    nextIndex = lindex;

                if (_compare(_heap[nextIndex], _heap[index]))
                {
                    _heap[0] = _heap[nextIndex];
                    _heap[nextIndex] = _heap[index];
                    _heap[index] = _heap[0];

                    index = nextIndex;
                }
                else
                {
                    break;
                }
                lindex = nextIndex * 2;
                rindex = lindex + 1;
            }

            return ret;
        }

        public virtual void Push(T item)
        {
            _heap.Add(item);

            int index = _heap.Count - 1, pindex = index / 2;

            while (pindex > 0)
            {
                if (_compare(_heap[index], _heap[pindex]))
                {
                    _heap[0] = _heap[index];
                    _heap[index] = _heap[pindex];
                    _heap[pindex] = _heap[0];
                }
                else break;

                index = pindex;
                pindex = index / 2;
            }
        }

        public void Clear()
        {
            _heap.Clear();
            _heap.Add(default(T));
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < _heap.Count; i++)
            {
                sb.Append(_heap[i]);
                sb.Append(',');
            }
            return sb.ToString();
        }

    }
}
